package middle;

public class Solution_316 {

    public static void main(String[] args) {
        Solution_316 model = new Solution_316();
        System.out.println(model.removeDuplicateLetters("a"));
        System.out.println(model.removeDuplicateLetters("bcabc"));
        System.out.println(model.removeDuplicateLetters("cbacdcbc"));
    }

    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        int[] lastIndexes = new int[26];
        boolean[] visited = new boolean[26];
        char[] array = new char[26];
        int index = -1;
        for (int i = 0; i < chars.length; i++) {
            lastIndexes[chars[i] - 'a'] = i;
        }
        for (int i = 0; i < chars.length; i++) {
            int offset = chars[i] - 'a';
            if (index < 0) {
                array[++index] = chars[i];
                visited[offset] = true;
            } else {
                if (!visited[offset]) {
                    while (index >= 0 && array[index] > chars[i] && lastIndexes[array[index] - 'a'] > i) {
                        visited[array[index] - 'a'] = false;
                        index--;
                    }
                    array[++index] = chars[i];
                    visited[offset] = true;
                }
            }
        }
        return new String(array, 0, index + 1);
    }
}
